๐Ÿ‘ฉโ€๐Ÿ’ป 42892. ๊ธธ ์ฐพ๊ธฐ ๊ฒŒ์ž„

@Seongukbaek Posted May 31, 2022 ยท Updated May 31, 2022 ยท 3 min read

๋ฌธ์ œ

Programmers - ๊ธธ ์ฐพ๊ธฐ ๊ฒŒ์ž„

๐Ÿ“ Logic

public void insert(Node input) { // root๊ฐ€ ์—†๋‹ค๋ฉด root ์ง€์ •, root๊ฐ€ ์žˆ๋‹ค๋ฉด, ์ž์‹ ๋…ธ๋“œ ํƒ์ƒ‰ํ•˜์—ฌ ์ €์žฅ if (root == null) root = input; else insert(input, root); } private void insert(Node input, Node root) { // ๋ถ€๋ชจ๋ณด๋‹ค x๊ฐ’์ด ์ž‘์€ ๊ฒฝ์šฐ์—๋Š” left๋ฅผ ํƒ์ƒ‰, ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด right ํƒ์ƒ‰ if (input.data.x < root.data.x) { if (root.left == null) root.left = input; else insert(input, root.left); } else { if (root.right == null) root.right = input; else insert(input, root.right); } }
  • ํŠธ๋ฆฌ๋ฅผ ์ƒ์„ฑํ•˜๋Š” ํ•จ์ˆ˜
  • ๋…ธ๋“œ์˜ x ์ขŒํ‘œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ ๋˜๋Š” ์˜ค๋ฅธ์ชฝ ์ž์‹ ์—ฌ๋ถ€๊ฐ€ ๊ฒฐ์ •๋œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Loc { int x; int y; int value; public Loc(int x, int y, int value) { this.x = x; this.y = y; this.value = value; } } class Node { Loc data; Node left; Node right; public Node(Loc data) { this.data = data; this.left = null; this.right = null; } } class Tree { Node root; int[] list; int size; int idx; public Tree(int size) { this.root = null; this.size = size; } public void insert(Node input) { // root๊ฐ€ ์—†๋‹ค๋ฉด root ์ง€์ •, root๊ฐ€ ์žˆ๋‹ค๋ฉด, ์ž์‹ ๋…ธ๋“œ ํƒ์ƒ‰ํ•˜์—ฌ ์ €์žฅ if (root == null) root = input; else insert(input, root); } private void insert(Node input, Node root) { // ๋ถ€๋ชจ๋ณด๋‹ค x๊ฐ’์ด ์ž‘์€ ๊ฒฝ์šฐ์—๋Š” left๋ฅผ ํƒ์ƒ‰, ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด right ํƒ์ƒ‰ if (input.data.x < root.data.x) { if (root.left == null) root.left = input; else insert(input, root.left); } else { if (root.right == null) root.right = input; else insert(input, root.right); } } public int[] preOrder() { list = new int[size]; idx = 0; preOrderTraversal(root); return list; } private void preOrderTraversal(Node n) { if (n == null) return; list[idx++] = n.data.value; preOrderTraversal(n.left); preOrderTraversal(n.right); } public int[] postOrder() { list = new int[size]; idx = 0; postOrderTraversal(root); return list; } private void postOrderTraversal(Node n) { if (n == null) return; postOrderTraversal(n.left); postOrderTraversal(n.right); list[idx++] = n.data.value; } } class Solution { public int[][] solution(int[][] nodeinfo) { ArrayList<Loc> locs = new ArrayList<>(); int size = nodeinfo.length; for (int i = 0; i < size; i++) locs.add(new Loc(nodeinfo[i][0], nodeinfo[i][1], i + 1)); // x๊ฐ’์€ ์˜ค๋ฆ„์ฐจ์ˆœ, y๊ฐ’์€ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ BFS ํ˜•์‹์œผ๋กœ ๋ณ€ํ™˜ locs.sort(((o1, o2) -> { if (o1.y == o2.y) return o1.x - o2.x; return o2.y - o1.y; })); Tree t = new Tree(size); for (Loc l : locs) t.insert(new Node(l)); return new int[][] {t.preOrder(), t.postOrder()}; } }

โœ๏ธ Review

  • ๊ณ ๋ฌธํ•ด์‹œ๊ฐ„์— BFS ํ˜•์‹์œผ๋กœ ์ž…๋ ฅ๋ฐ›์•„ ์ด๋ฅผ preorder, postorder๋กœ ์ถœ๋ ฅํ–ˆ๋˜ ๊ณผ์ œ๊ฐ€ ์ƒ๊ฐ๋‚˜ ์•„์ด๋””์–ด๋Š” ์‰ฝ๊ฒŒ ์žก์„ ์ˆ˜ ์žˆ์—ˆ๋‹ค.
  • x๊ฐ’ ์ขŒํ‘œ์— ๋”ฐ๋ฅธ ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ ์ž์‹ ์—ฌ๋ถ€์— ๋Œ€ํ•œ ๊ณ ๋ ค๋ฅผ ํ†ตํ•ด ํŠธ๋ฆฌ๋ฅผ ์ƒ์„ฑํ•ด์•ผ ํ•˜๋Š” ์ƒ๊ฐ์ด ํ‚ค ํฌ์ธํŠธ์˜€์ง€ ์•Š์„๊นŒ ..

    • insert() ๋ฅผ ์˜ค๋ฒ„๋กœ๋”ฉํ•˜๋Š” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•ด๋ณด์•˜๋‹ค!
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€